package stack;

/**
 * 用数组或链表实现
 * 先进后出
 * 栈是限制线性表中元素的插入、删除只能在线性表的同一端进行的特殊线性表
 * 允许插入的一端称为栈顶，另一端称为栈底
 *
 * 应用场景
 * 1.子程序调用：在跳往子程序前，会将下个指令的地址存到堆栈中，直到子程序
 * 执行完后再将地址取出，以回到原来的程序中。
 * 2.处理递归调用：和子程序调用类似，但除了储存下一个指令地址外，将参数、区域
 * 变量等数据也存入堆栈中。
 * 3.表达式转换【中缀表达式转后缀表达式】与求值（实际解决）
 * 4.二叉树遍历
 * 5.图形深度优先（depth-first）搜索法
 */
public class StackDemo {
    public static void main(String[] args) {

    }
}

/**
 * 用数组模拟栈
 */
class ArrayStack {
    private int maxSize; //栈的大小
    private int[] stack;//数组 模拟栈
    private int top = -1;//指针，表示栈顶

    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }

    public boolean isFull() {
        return top == maxSize - 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public void push(int value) {
        if (isFull()) {
            System.out.println("满");
            return;
        }
        top++;
        stack[top] = value;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("空");
        }
        int value = stack[top];
        top--;
        return value;
    }

    public void list() {
        if (isEmpty()) {
            System.out.println("空");
            return;
        }
        for (int i = top; i > -1; i--) {
            System.out.println(stack[i]);
            i--;
        }
    }
}

/**
 * 用链表模拟栈
 */
class ListStack {
    private int no;
    private Node head;

    public ListStack(int no) {
        this.no = no;
    }

    public void push(Node node) {
        Node temp = head;
        if (temp.next == null) {
            temp.next = node;
        }
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = node;
    }

    public int pop() {
        Node temp = head;
        if (temp.next == null) {
            throw new RuntimeException("栈为空");
        }
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        return temp.no;
    }

    public void list() {
        Node temp = head;
        if (temp.next == null) {
            throw new RuntimeException("栈为空");
        }
        int a = 0;
        while (true) {
            if (temp.next == null) {
                break;
            }
            a++;
            temp = temp.next;
        }
        for (int i = 0; i < a; i++) {
            int b = pop();
            System.out.println(b);
        }
    }

    public void update(Node node) {
        //假设有序
        Node temp = head;
        if (temp.next == null) {
            System.out.println("栈为空");
            return;
        }
    }
}
//链表  定义节点
class Node{
    public int no;
    public Node next;//指向下一个节点

    public Node(int no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", next=" + next +
                '}';
    }

}
